package array.Binary_Search;
/*
        给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
        如果数组中不存在目标值 target，返回 [-1, -1]。
        你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

        示例 1：
        输入：nums = [5,7,7,8,8,10], target = 8
        输出：[3,4]

        示例 2：
        输入：nums = [5,7,7,8,8,10], target = 6
        输出：[-1,-1]

        示例 3：
        输入：nums = [], target = 0
        输出：[-1,-1]
        */
public class lc34 {
    public static void main(String[] args) {
        int[] nums=new int[]{2,2};
        int[] result=searchRange(nums,2);
        for (int val: result
             ) {
            System.out.println(val);
        }

    }
    public static int[] searchRange(int[] nums, int target) {
        int[] result=new int[2];
        if(nums.length==0||nums[0]>target||nums[nums.length-1]<target){
            result[0]=-1;
            result[1]=-1;
            return result;
        }//当数组长度为0，或者所给数字超出数组范围时直接返回[-1,-1]

        //找到target数字的位置
        int location=-1;
        int low=0;
        int high=nums.length-1;
        int mid=(low+high)>>1;
        while(low<=high){
            mid=(low+high)/2;
            if(nums[mid]<target){
                low=mid+1;
            }else if(nums[mid]>target){
                high=mid-1;
            }else if(nums[mid]==target){
                location=mid;
                break;
            }
        }
        System.out.println("位置为："+location);
        if(location<0){
            result[0]=-1;
            result[1]=-1;
            return result;
        }else{
            int left=location;
            int right=location;
            int i=1;
            while((location+i)<=nums.length-1&&nums[location+i]==target){  //这里判断数组是否越界放在前面，编译器先判断前面的条件，若为false，则不看后面的条件了
                i++;  //如果先把nums[location+i]==target写上可能会数组越界报错
            }
            right+=(i-1);
            i=1;
            while((location-i)>=0&&nums[location-i]==target&&(location-i)>=0){
                i++;
            }
            left-=(i-1);
            result[0]=left;
            result[1]=right;
            return result;
        }
    }
}
